package arithmetic.leetCode.yi;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: yilin
 * Date: 2019-07-31
 * Time: 16:37
 */
public class IntersectionNode {


    public class ListNode {

        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public static ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        int lengthA = getLength(headA);
        int lengthB = getLength(headB);
        int diff = lengthA - lengthB;
        ListNode curA = diff >= 0 ? headA : headB;
        ListNode curB = diff < 0 ? headA : headB;

        diff = Math.abs(diff);
        while (diff > 0) {
            curA = curA.next;
            diff--;
        }

        while (curA != null && curB != null && curA != curB) {
            curA = curA.next;
            curB = curB.next;
        }
        return curA;
    }


    public static int getLength(ListNode listNode) {
        int length = 0;
        ListNode temp = listNode;
        while (temp != null) {
            temp = temp.next;
            length++;
        }
        return length;
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        /**
         定义两个指针, 第一轮让两个到达末尾的节点指向另一个链表的头部, 最后如果相遇则为交点(在第一轮移动中恰好抹除了长度差)
         两个指针等于移动了相同的距离, 有交点就返回, 无交点就是各走了两条指针的长度
         **/
        if (headA == null || headB == null) return null;
        ListNode pA = headA, pB = headB;
        // 在这里第一轮体现在pA和pB第一次到达尾部会移向另一链表的表头, 而第二轮体现在如果pA或pB相交就返回交点, 不相交最后就是null==null
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }

}
